This invention relates to arithmetic units for high speed data processors and particularly to the multiply/divide features of such units.
In a data processor which has multiply/divide cicuitry, the multiplication process is performed essentially as a series of additions, and division is handled essentially as a series of subtractions, usually in the form of complemental subtractions. Multiplying operations commonly are speeded up by using carry save adders to perform the successive additions. A carry save adder operates in such a fashion that it does not immediately combine the carry bits with the basic sum bits (sometimes referred to as half-sum bits) that result from each addition but instead holds these sum and carry bits temporarily in separate registers until a subsequent time when they can be conveniently combined. This procedure saves the time that otherwise might be spent waiting for carries to be "rippled" or propagated through a long string of sum bits following each addition instead of being held in abeyance so as to permit the next cycle of multiplication to proceed.
In data processors that have divider units, the divider circuitry customarily employs some type of adder other than a carry save adder. As stated above, division involves a succession of subtractions usually performed as additions wherein one of the terms is inverted to complemental form. Each subtraction must be examined to ascertain whether it is "successful" or "unsuccessful" before the next subtraction can proceed. An unsuccessful subtraction is one which results in an overdraft because the subtrahend (i.e., the divisor in a division problem) is of greater magnitude than the true value of the minuend (i.e., the current remainder left from the preceding subtraction, if any, or the initial dividend value in the case of the first subtraction). The overdraft must either be anticipated and prevented by not actually performing the subtraction, or if the subtraction has been performed, it must be nullified by restoring the previous minuend value and correspondingly readjusting the value of the digit in the current order of the quotient value. It is considered preferable to anticipate an overdraft and prevent the subtraction from occurring rather than perform the subtraction and then have to restore the previous minuend value.
Adders that customarily are employed in dividers do not resemble the carry save adders commonly used in multipliers. A carry save adder deliberately withholds the effect of the carries that have been generated during a current addition step until the next addition step is performed. In principle this is opposed to a "lookahead" function, which would require that the effect of the carries resulting from one step in the arithmetic process be ascertained before the next step in that process is performed. Consequently, it has been the general practice to provide separate adders for the multiply and divide functions, using a carry save adder in the multiplier and a different type of adder, preferably one having lookahead capability, in the divider of the data processor. Hence, in conventional practice the provision of a dividing function makes the arithmetic unit of the processor much more costly and also requires the provision of extra space for an additional adder. Moreover, while a conventional lookahead adder will save some of the time that otherwise would be wasted in performing a futile subtraction and then countermanding it, such an adder does not utilize a completely "nonperforming" method but requires that some time be spent in actually performing at least part of the subtraction process, which time is wasted if the subtraction attempt is found to be unsuccessful.